The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. Often this is not an issue with machine learning approaches, which shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. Inspired by a recent line of work, we augment three well-known online settings with machine learned predictions about the future, and develop algorithms that take them into account. In particular, we study the following online selection problems: (i) the classical secretary problem, (ii) online bipartite matching and (iii) the graphic matroid secretary problem. Our algorithms still come with a worst-case performance guarantee in the case that predictions are subpar while obtaining an improved competitive ratio (over the best-known classical online algorithm for each problem) when the predictions are sufficiently accurate. For each algorithm, we establish a trade-off between the competitive ratios obtained in the two respective cases.

Summary and Contributions: Recently there has been a spate of work in online algorithms combining traditional online algorithms with "machine learned" advice. In such problems, one has access to an exogenous prediction about the problem, and one hopes for best of both worlds guarantees of the form: "if the prediction is good, then I do really well (beating the worst-case benchmark), but if the prediction is bad, then I still do (approximately) at least as well as the worst-case benchmark". In the secretary problem, you observe a stream of n real numbers that arrives in a uniformly random order. Your goal is to choose the largest element (or at least achieve a good approximation to the largest element). In the setting with advice, you are given a prediction p of the maximum value of all n real numbers.

The reviewers urge the authors to improve the discussion on how to set c and \lambda, particularly given their relationship with each other.

The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. Often this is not an issue with machine learning approaches, which shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. Inspired by a recent line of work, we augment three well-known online settings with machine learned predictions about the future, and develop algorithms that take them into account. In particular, we study the following online selection problems: (i) the classical secretary problem, (ii) online bipartite matching and (iii) the graphic matroid secretary problem. Our algorithms still come with a worst-case performance guarantee in the case that predictions are subpar while obtaining an improved competitive ratio (over the best-known classical online algorithm for each problem) when the predictions are sufficiently accurate.